\section{Problema 1: Pascual y el correo}

\subsection{Introducción}
En un centro de distribución de correo, se reciben paquetes todos los días y se los distribuye en camiones para enviarlos a la sede central. El encargado de logística, Pascual, utiliza el siguiente sistema para distribuir los paquetes: al llegar un paquete, intenta ubicarlo en algún camión, eligiendo el que tenga menos peso actualmente; sin embargo cada camión soporta un peso máximo (igual para todos), entonces en el caso en que Pascual no pueda colocar el paquete en el camión elegido sin que supere su máxima capacidad, tendrá que colocarlo en uno nuevo.

El problema consiste en escribir un algoritmo que, dado los pesos de todos los paquetes en el orden en que fueron llegando, y el peso máximo de todos los camiones, devuelva el peso que tiene cada camión usado al finalizar el día.

Por ejemplo, si se tiene el siguiente formato de entrada: 

\begin{verbatim}
INPUT: 200 5 150 40 30 200 70 | OUTPUT: 3 190 100 200
\end{verbatim}

\begin{center}
\begin{tabular}{|c||c|c|} \hline
Camión & Paquetes & Peso total \\ \cline{1-3}
$c_{1}$ & 150,40 &  190 \\ \cline{1-3}
$c_{2}$ & 30,70 & 100 \\ \cline{1-3}
$c_{3}$ & 200 & 200 \\  \cline{1-3}
\end{tabular}
\end{center}

\subsection{Desarrollo}
Para obtener la solución deseada, sólo bastó con desarrollar un algoritmo que se comportara como el método de Pascual para guardar paquetes, con la única condición de respetar la complejidad pedida. Para ello, se definieron los tipos \textit{Paquete} (un \textit{int} que representa el peso de cada paquete) y \textit{Camión} (un \textit{int} que representa el peso que contiene cada camión).

La estructura de datos utilizada para asegurar que la complejidad no sea cuadrática, fue el heap de la STL \footnote{ $http://www.cplusplus.com/reference/algorithm/make\_heap/$ }. La ejecución comienza con un vector de camiones vacío al cual se le agrega el primer elemento de valor $0$. Luego se ``heapifica'' el heap mediante la función \texttt{make\_heap}. Este nuevo árbol tendrá siempre en la raíz el camión que menos peso esté cargando (es decir, un $minHeap$). Después hay que recorrer el vector de paquetes, uno por uno. Posteriormente se verifica que pueda colocarse el paquete actual en el primer camión del heap. Si se puede, se suma el valor del paquete al del camión, y sino, se agrega un nuevo camión al árbol que tiene como peso inicial el valor del paquete. Finalmente se continúa la iteración con el próximo paquete.

Se puede observar el pseudocódigo del algoritmo en la sección \ref{complejidad1}

\subsubsection{Correctitud}
Demostrar la correctitud de un algoritmo consiste en demostrar por qué el algoritmo devuelve el resultado correcto al problema planteado. En este caso, el problema ya indica cuáles deben ser los pasos a seguir por el algoritmo, que es utilizar el método de Pascual de colocar los paquetes en orden de llegada en el camión con más lugar disponible. El desafío es lograr encontrar una estructura de datos adecuada, que devuelva el camión con menos carga en tiempo menor al cuadrático sobre la cantidad de paquetes totales. Pero eso se analizará en la sección \ref{complejidad1}. Dada la estructura del $minHeap$, se puede asegurar que al agregar o modificar un elemento y luego reordenar, en la raíz siempre quedará el elemento de menor valor (ver pie de página), por lo que el algoritmo en cada iteración tomará el camión más vacío y en caso de no poder colocarse el paquete se agregará su valor al heap como un nuevo camión. Este es, efectivamente, el método de Pascual.

\subsection{Análisis de complejidad}\label{complejidad1}
Sean $n$ la cantidad de paquetes y $m$ la cantidad de camiones usados, la complejidad de cada instancia se comenta en el siguiente pseudocódigo:

\begin{algorithm}

    \SetKwInOut{Input}{input}
    \SetKwInOut{Output}{ouput}
    \SetKwComment{Complejidad}{\color{Blue}$\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidad}{\color{Red}$\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidad}{\color{Fuchsia}$\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}
    \SetKwComment{ComplejidadTotal}{\color{Blue}Complejidad total $\rhd$ $\mathcal O($}{\color{Blue}$\mathcal )$}
    \SetKwComment{SubComplejidadTotal}{\color{Red}Complejidad total $\square$ $\mathcal O($}{\color{Red}$\mathcal )$}
    \SetKwComment{SubSubComplejidadTotal}{\color{Fuchsia}Complejidad total $\fullmoon$ $\mathcal O($}{\color{Fuchsia}$\mathcal )$}

    \SetKwData{A}{A}
    \SetKwData{n}{n}

    \Input{Vector de paquetes \texttt{paquetes}, Vector de camiones \texttt{camiones}, entero \texttt{pesoMaximo}}
    \Output{Vac\'io}
    % \BlankLine
    agregar camión vacío al vector solución \Complejidad*[r]{\color{blue}$1$}
    crear un heap a partir del vector anterior, con \texttt{make\_heap} \Complejidad*[r]{\color{blue}$m$}
    \For(\Complejidad*[f]{\color{Blue}$n$}){$paquete\_i$ con $[$ i $|$ $0 ... n$ $)$}{
    	\If{el $paquete\_i$ no supera el \texttt{pesoMaximo} en el camión con menos carga}{
    	    agregar $paquete\_i$ al camión con menos carga del heap \Complejidad*[r]{\color{blue}$log(m)$}
    	\Else{agregar nuevo camión al heap, con carga inicial de $paquete\_i$ \Complejidad*[r]{\color{blue}$log(m)$}}}
    }
    \caption{Ejercicio 1 - Pseudocódigo y Complejidad}
    \label{pseudocodigo1}
\end{algorithm}

Sabemos que todos los paquetes recibidos podrán ser cargados en algún camión, ya que todos tienen peso menor o igual al máximo permitido por los camiones. 
Por lo tanto, como mucho tendremos $n$ camiones en uso. Es decir, uno por paquete. Por ello podemos acotar $log(m)$ por $log(n)$. 
Como este proceso de reorganizar el heap se hace una vez por cada paquete nuevo, la complejidad es igual a $O(n \cdot log(n))$.

Por otro lado, agregar el $paquete\_i$ al camion con menos carga del heap implica tomar el primer cami\'on de la lista (que es el de carga m\'inima), pornerlo al final, modificar su valor agreg\'andole el $paquete\_i$ (hasta ahora todas operaciones en $O(1)$) y luego acomodar el cami\'on con su nuevo peso en el heap de camiones (lo que cuesta $O(log(m))$)

\subsection{Análisis de casos}
Tomamos como primer caso borde aquel en el que la cantidad de paquetes sea nula. El algoritmo prevé dicho caso y antes de llamar a la función que resuelve el problema (al terminar de levantar los datos de entrada), corrobora que la cantidad de paquetes sea mayor a cero. Si no lo es, devuelve cero, ya que no se utilizó ningún camión en la presente instancia.

\begin{verbatim}
>> INPUT: 200 0 | OUTPUT: 0
\end{verbatim}

Luego, si solo tenemos un paquete, el algoritmo se percata de que la cantidad de paquetes ingresados es mayor a cero. Por lo tanto comienza a resolver el problema y luego de una única iteración devuelve los datos esperados, es decir, que utilizó un único camión cuya carga es igual al peso del paquete.

\begin{verbatim}
>> INPUT: 200 1 100 | OUTPUT: 1 100
\end{verbatim}

También podemos considerar que todos los paquetes ingresados entran en un único camión. Por lo tanto el algoritmo siempre tomará el mismo camión usado previamente, ya que analizará el espacio libre en el mismo y concluirá que puede ser efectuada la carga. Finalizará la ejecución solo con este camión presente, cuyo peso será igual a la sumatoria de todos los paquetes.

\begin{verbatim}
>> INPUT: 200 5 25 75 30 60 10 | OUTPUT: 1 200
\end{verbatim}

En contrapartida, observamos el caso contrario, que todos los paquetes ocupen la totalidad de cada camión utilizado. Es decir que todos los paquetes tengan como peso la máxima carga posible. En este caso, siempre se necesitará un nuevo camión, ya que nunca tendremos el espacio requerido en el camión con menos carga. La solución a la instancia, en esta oportunidad, será que la cantidad de camiones utilizados es igual a la de paquetes presentes en el sistema, y que las cargas de cada camión corresponderá al peso de uno de los paquetes en cuestión.

\begin{verbatim}
>> INPUT: 200 5 200 200 200 200 200 | OUTPUT: 5 200 200 200 200 200
\end{verbatim}

Finalmente, un ejemplo de caso promedio, creado con nuestro algoritmo de generación de instancias pseudo-aleatorias. La construcción y uso del mismo se puede leer en la sección \ref{ejecucion1}.

\begin{verbatim}
>> INPUT: 200 10 137 40 126 109 98 104 79 4 89 139 | OUTPUT: 6 109 177 126 177 197 139
\end{verbatim}

\subsection{Test de performance}
Sabiendo la complejidad de nuestro algoritmo, veamos en la práctica si la misma se cumple. Para esto diseñamos \texttt{generador}, que crea instancias pseudo-aleatorias con diferentes cantidades de paquetes; desde uno solo hasta cierta cantidad pasada como parámetro. Fijamos esta cantidad en 500 para tener muchas instancias (sin alcanzar un número excesivo) dentro de una amplia variedad de situaciones posibles. Estas instancias son puestas a prueba bajo el ejecutable \texttt{test\_performance}, que analiza cada una de las 500 instancias una cierta cantidad de veces, nuevamente pasada como argumento. De esta manera, calcula los ``ciclos de clock'' utilizados en promedio para cada una de dichas instancias.
Todos estos valores devueltos son graficados junto con una curva de la familia $n \cdot log(n)$, para visualizar como los datos están acotados por la misma.

\begin{center}
    \includegraphics[scale=0.72]{./img/compProm.png}    \\
     \small{\textbf{Figura 1}: 500 instancias, con 100 iteraciones por cada una - Carga máxima: 600}
    \label{fig:fig1}
\end{center}

Luego, observamos el rendimiento del algoritmo en diversas situaciones puntuales que ya habíamos considerado previamente. Las instancias a analizar ahora son las siguientes:

\begin{itemize}
    \item Paquetes con cargas descendientes: es decir que dado el iésimo paquete, todos los paquetes posteriores serán de menor o igual carga.
    \item Paquetes con cargas ascendentes: en este caso, dado el iésimo paquete todos los que ingresan luego, tendrán una carga mayor o igual al mismo.
    \item Paquetes con cargas máximas: todos los paquetes de la secuencia tienen la misma carga, la máxima permitida por los camiones.
    \item Paquetes con cargas aleatorias: idéntico al caso que analizamos en la gráfica anterior. Son paquetes cuyas cargas siguen una distribución uniforme.
\end{itemize}

Todos los valores serán graficados en el mismo gráfico para comparar los resultados. A su vez, nuevamente incluímos una función de la familia $n \cdot log(n)$ para corroborar que la complejidad indicada se cumple en todos los casos analizados.

\begin{center}
    \includegraphics[scale=0.7]{./img/compCasos.png}  \\
    \small{\textbf{Figura 2}: 500 instancias, con 100 iteraciones por cada una - Carga máxima: 600}
    \label{fig:fig2}
\end{center}

Podemos observar que no hay mucha variación entre los cuatro casos comparados, en relación a la cota de complejidad mencionada (recordemos, $O(n \cdot log(n))$). Se ve que a partir de aquellas instancias que tienen una cantidad de paquetes mayor a 300, la cota esperada sobrepasa los tiempos medidos empíricamente.

Ahora podemos analizar un poco mas en detalle que es lo que ocurre en cada caso.

¿Por qué vemos que las instancias con cargas descendientes consumen mas tiempo de ejecución que las de cargas máximas cuando el tamaño de la entrada es menor a 400 paquetes? Esto es porque al principio, el programa recibe paquetes demasiado "pesados" solamente (para mas detalles sobre como fueron generadas las instancias, ver la sección \ref{ejecucion1}). Y por lo tanto, todo el tiempo está ingresando nuevos camiones al heap. Pero estos camiones no son cualquier camión, sino que son un nuevo camión con carga igual al peso del paquete actual. Y como la instancia cumple la condición de ser descendiente, el paquete actual es el de mínimo peso por el momento. Entonces el camión es el que tiene menor carga y debe ser ubicado correctamente en el heap, por lo tanto ingresarlo al mismo es mas costoso que ingresar un camión que por el contrario, tuviera el peso máximo.

Siguiendo este mismo razonamiento, cuando en el caso de las instancias con cargas máximas llega un nuevo paquete, es sabido que se va a tener que utilizar un nuevo camión (ya que el paquete actual tiene peso máximo por ser ésta una instancia que cumple con la condición de tener todas las cargas máximas). Pero este nuevo camión tiene igual carga que el peso del paquete actual, que es el máximo aceptado. Por lo tanto al ingresarlo al heap, no se deberá reorganizar el mismo, ya que éste elemento será maximal.

En contrapartida, observamos que en dicho intervalo del gráfico, las instancias con cargas ascendientes permanecen en su mayoría por debajo del tiempo consumido por sus pares de cargas máximas. Esto sucede porque en estas circunstancias, las instancias entregan al programa paquetes mucho mas "livianos" y por lo tanto se podrían llegar a cargar en el mismo camión... pero, para poder hacer eso tendríamos que modificar el camión con menor carga, ubicarlo al final del heap y reubicarlo nuevamente... ¿por que no obtengo el mismo costo temporal que en el caso de las cargas descendientes?. La respuesta es simple, porque el heap crece mucho mas lento en estas instancias, ya que al poder cargar varios paquetes en el mismo camión, nos deshacemos de una cantidad importante de elementos en el vector. De esta manera, reorganizar el heap cuesta menos que en el caso análogo.

Podemos observar como en las instancias finales, los casos se asemejan mas entre sí. De hecho, el caso que podríamos llamar "promedio" (lo que uno esperaría habitualmente serían instancias con paquetes sin orden alguno, es decir, cargas aleatorias) es muy similar al caso de cargas máximas durante todo el gráfico. Tiene un consumo temporal levemente menor, ya que varios paquetes se deben acumular en un mismo camión. Pero el crecimiento del heap igualmente es bastante grande. Esto se debe a la distribución que siguen los paquetes. En este caso es una distribución uniforme, por lo tanto en instancias con un tamaño de entrada bastante grande, la cantidad de paquetes livianos y de paquetes pesados es prácticamente la misma.

\subsection{Compilar y ejecutar}\label{ejecucion1}

El programa que resuelve el ejercicio se encuentra escrito en el archivo \texttt{pro1/src/main.cpp}. Para compilarlo hay que llamar a \texttt{make} en una terminal. Una vez hecho esto, se lo puede ejecutar mediante \texttt{./pro1 < \hspace{1bp} nombre\_input.txt}, donde \texttt{nombre\_input.txt} es el archivo con las instancias del problema.
Luego de hacer las acciones pertinentes, la aplicación devolverá por pantalla las soluciones de cada una de las instancias que se encuentran en el archivo de entrada, junto con la cantidad de camiones utilizados en la misma.

También se puede correr el test de performance, ejecutando \texttt{make test\_performance} (en el path \texttt{pro1/etc/}). Luego lo ejecutamos escribiendo \texttt{./test\_performance < \hspace{1bp} input.txt}, donde \texttt{input.txt} representa el archivo donde están escritas las instancias a resolver. En el comienzo del fichero se debe escribir en una nueva línea, la cantidad de iteraciones a realizar. Los resultados se guardarán en un nuevo fichero creado automáticamente llamado \texttt{res\_performance.txt} (cantidad de paquetes de la instancia resuelta y cantidad de tiempo requerido en promedio, según las iteraciones ingresadas como parámetro, para resolver esa instancia).

Con \texttt{make generador} (también en el path \texttt{pro1/etc/}), podemos compilar el programa que genera un archivo con instancias pseudo-aleatorias. Para ejecutarlo, debemos escribir \texttt{./generador modo output.txt cant cargaMax}, donde \texttt{modo} es un entero entre 1 y 4 (a saber, ``1'' es para crear instancias con paquetes aleatorios (según funciones de la STL, siguiendo una distribución uniforme), ``2'' para construir instancias con cargas ascendentes, ``3'' para el caso con cargas descendentes y ``4'' para casos con cargas máximas), \texttt{output.txt} sería el destino de las instancias generadas, \texttt{cant} sería la cantidad de instancias a generar (sea $n$ el valor ingresado, se crearán $n$ instancias, una para cada $i$ entre 1 y $n$) y \texttt{cargaMax} que es el valor que elegimos como cota superior para todas las cargas máximas de todas las instancias generadas (ya que las cargas máximas de cada una de las $n$ instancias será elegida también ``aleatoriamente'').
